/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
	TreeNode* dfs(TreeNode* A, TreeNode* B)
	{
		if (A == nullptr)
		{
			return nullptr;
		}
		if (A->val == B->val)
		{
			return A;
		}
		TreeNode* left = dfs(A->left, B);
		TreeNode* right = dfs(A->right, B);

		if (left)
		{
			return left;
		}
		else if (right)
		{
			return right;
		}
		else
			return nullptr;

	}

	bool isvalid(TreeNode* A, TreeNode* B)
	{
		if (A == nullptr && B == nullptr)
		{
			return true;
		}


		if (A == nullptr && B != nullptr)
		{
			return false;
		}
		else if (A != nullptr && B == nullptr)
		{
			return true;
		}
		else if (A->val != B->val)
		{
			return false;
		}
		return isvalid(A->left, B->left) && isvalid(A->right, B->right);
	}
	bool isSub(TreeNode* A, TreeNode* B)
	{
		if (A == nullptr)
		{
			return false;
		}

		TreeNode* cur = dfs(A, B);
		if (cur == nullptr)
		{
			return false;
		}
		if (isvalid(cur, B))
		{
			return true;
		}
		else
		{
			return isSub(cur->left, B) || isSub(cur->right, B);
		}

	}
	bool isSubStructure(TreeNode* A, TreeNode* B) {
		if (B == nullptr)
		{
			return false;
		}

		return isSub(A, B);
	}
};